package leetcode.median;

import leetcode.base.ListNode;

public class $143_ReorderList {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        // 找到链表中点
        ListNode mid = getMid(head);
        ListNode middle = mid.next;
        mid.next = null;

        // 翻转链表
        ListNode reverseHead = reverseList(middle);
        //合并链表
        ListNode p = head;
        ListNode q = reverseHead;
        while (p != null && q != null) {
            ListNode pNext = p.next;
            p.next = q;
            ListNode qNext = q.next;
            q.next = pNext;
            p = pNext;
            q = qNext;
        }
    }

    public ListNode getMid(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}
